package lec07datastructure.v2;

public class MyLinkedList {
    static class Node {
        int data;
        Node prev, next;

        public Node(int data) {
            this(data, null, null);
        }

        public Node(int data, Node prev, Node next) {
            this.data = data;
            this.prev = prev;
            this.next = next;
        }
    }

    Node head = new Node(0);
    Node tail = new Node(0);
    int size = 0;

    MyLinkedList() {
        head.next = tail;
        tail.prev = head;
        size = 0;

    }

    void pushBack(Node node) {
        preInsert(node, tail);
    }

    void preInsert(Node q, Node r) {
        Node p = r.prev;
        postInsert(q, p);
    }

    void delete(Node q) {
        if (size == 0) return;
        Node p = q.prev;
        Node r = q.next;
        p.next = r;
        r.prev = p;
        --size;


    }

    void popFirst() {
        if (size > 0)
            delete(head.next);
    }

    void popLast() {
        if (size > 0)
            delete(tail.prev);
    }

    void postInsert(Node q, Node p) {
        Node r = p.next;
        p.next = q;
        q.prev = p;
        r.prev = q;
        q.next = r;
        ++size;
        return;
    }

    public void pushFirst(Node node) {
        postInsert(node, head);
    }

    //O(n)实现访问第k个元素
    Node get(int idx) {
        if (idx >= size) return null;
        if (idx < size >> 1) {
            Node p = head;
            while (idx-- > 0) p = p.next;
            return (p);
        } else {
            Node p = tail;
            idx = size - 1 - idx;
            while (idx-- > 0) p = p.prev;
            return p;
        }

    }

    @Override
    public String toString() {
        StringBuffer buffer = new StringBuffer("[");
        Node node = head.next;
        while (node != tail) {
            buffer.append(node.data + ",");
            node = node.next;
        }
        buffer.setCharAt(buffer.length() - 1, ']');
        return buffer.toString();

    }


    public static void main(String[] args) {
        MyLinkedList list = new MyLinkedList();
        for (int i = 0; i < 10; i++) {
            list.pushBack(new Node(i));
        }
        for (int i = 10; i < 20; i++) {
            list.pushFirst(new Node(i));
        }
        System.out.println(list);
        while (list.size > 0) {
            System.out.println(list);
            list.delete(list.head.next);
        }
    }


}
